This invention relates to the field of object-oriented programming and, more specifically, to extensible and efficient double dispatch in single-dispatch object-oriented programming languages.
Three concepts are central to object-oriented programming: encapsulation, inheritance, and polymorphism. Encapsulation refers to how implementation details are hidden by an abstraction called an xe2x80x9cobject.xe2x80x9d An object is said to encapsulate code and data as defined by a xe2x80x9cclass,xe2x80x9d of which the object is an xe2x80x9cinstance.xe2x80x9d An object is created by xe2x80x9cinstantiatingxe2x80x9d its class. The class specifies the code and data associated with each instance. A xe2x80x9cconcrete classxe2x80x9d includes all the code necessary for instances to work correctly and may thus be instantiated. An xe2x80x9cabstract classxe2x80x9d may have some of the code or no code at all. Hence, it cannot be instantiated.
An object-oriented software system is made up of objects interacting with one another by xe2x80x9csending messages,xe2x80x9d also known as xe2x80x9ccalling operations.xe2x80x9d The set of messages (operations) that an object understands is called its xe2x80x9cinterface.xe2x80x9d An object implements its response to a message in a xe2x80x9cmethodxe2x80x9d that is common to all instances of the object""s class. A method typically elicits collateral message sends. Objects are unaware of each other""s implementations. Objects only know the messages to which other objects can respond. Encapsulation controls complexity by partitioning the software system into small, well-defined pieces, and it makes it easy to change part of the system without affecting other parts.
Inheritance defines classes in terms of other classes. Class B that inherits from class A is called a xe2x80x9csubclassxe2x80x9d or xe2x80x9cderived classxe2x80x9d of class A (which is called the xe2x80x9cparent class,xe2x80x9d xe2x80x9cbase class,xe2x80x9d or xe2x80x9csuperclassxe2x80x9d). Class C derived from B may be termed a xe2x80x9cdescendantxe2x80x9d of A as opposed to a xe2x80x9csubclass.xe2x80x9d The subclass responds to the same messages as its parent, and it may respond to additional messages as well. The subclass xe2x80x9cinheritsxe2x80x9d its implementation from its parent, although it may choose to re-implement some methods, add more data, or both. An abstract class may explicitly defer implementation of a method to subclasses. Such a method (or operation) is termed xe2x80x9cabstractxe2x80x9d as it has no implementation. Non-abstract operations are sometimes called xe2x80x9cconcrete operations.xe2x80x9d Inheritance lets programmers define new classes easily as incremental refinements of existing ones. It also enables polymorphism.
Polymorphism refers to the substitutability of related objects. Objects are xe2x80x9crelatedxe2x80x9d if they have the same xe2x80x9ctype,xe2x80x9d and in most object-oriented languages that means they are instances of the same class, or they have a common superclass through inheritance. Objects of the same type are said to have xe2x80x9ccompatible interfaces.xe2x80x9d
Objects with compatible interfaces may be treated uniformly, that is, without regard to their specific type. For example, a Graphic class that defines an abstraction for graphical objects may define a Draw method. The Graphic class might have subclasses Rectangle and Circle that re-implement Draw to draw a rectangle and circle, respectively. Polymorphism allows Rectangle and Circle instances to be treated uniformly as Graphic objects. In other words, all one needs to know to tell an object to draw itself is that the object is an instance of a Graphic subclass. Whether the object is an instance of Rectangle or Circle is immaterial; one can send it the Draw message without knowing its exact type (e.g., Rectangle or Circle).
Declaring the type of an object explicitly in the program lets the compiler ensure that objects are sent only messages that they implement. Compile-time checks for type incompatibility are valuable because they can catch common programming errors. If a program contains code that attempts to send a message to an object that does not implement a corresponding methodxe2x80x94a coding errorxe2x80x94then the compiler can detect it before the program is ever run. A compiler that performs such checks is said to enforce xe2x80x9cstatic type safety.xe2x80x9d
However, a programmer may circumvent the type checks run by the compiler through programming language mechanisms such as casts and run-time type tests. The former coerces an object to a particular (and possibly incompatible) type, while the latter tests the type of an object and performs computation based on the outcome of the test. Because these mechanisms are invoked at run-time, they are usually beyond the ability of the compiler to check. Thus they may induce type-related failures at run-time. Programs that can fail in this way are called xe2x80x9ctype-unsafe.xe2x80x9d
An important goal of software design generally, and object-oriented design in particular, is to permit change in functionality without change in existing codexe2x80x94additive change instead of invasive change. Polymorphism furthers this goal by letting programmers write general code that can be customized later without change. Suppose there is code that draws pictures by sending Draw messages to a set of Graphic instances. Rectangle and Circle objects may be passed to such code, and it will tell the objects to draw themselves. Later, a new subclass of Graphic can be defined, say Polygon, implementing its Draw method appropriately. Because Polygon is a subclass of Graphic, instances of Polygon may be passed to the picture-drawing code, and it will draw polygons in the picturexe2x80x94with no modification whatsoever.
This example of polymorphism illustrates xe2x80x9csingle dispatchxe2x80x9d: the code that executes in response to a message depends on the message (e.g., Draw) and the type of the receiver (Rectangle, Circle, etc.). It is also possible to dispatch on more than one type. Suppose one wants to draw a polygon either on the display or on hardcopy. The code for drawing a polygon on the display is likely to differ drastically from the code that prints it out. One could therefore define a class Device that abstracts the output device, with subclasses Display and Printer. If a programming language allows one to dispatch on two typesxe2x80x94the Graphic subclass and the Device subclassxe2x80x94then the language supports xe2x80x9cdouble dispatch,xe2x80x9d as the code that executes in response to a message send (e.g., Draw) depends on the message and the type of two receivers (e.g., Circle and Printer). Single and double dispatch exemplify the more general notion of xe2x80x9cmultiple dispatch,xe2x80x9d which permits dispatch on any number of types.
Mainstream object-oriented programming languages such as C++, Eiffel, Java, and Smalltalk support only single dispatch directly. Double and higher-order dispatch must be implemented explicitly in such languages. The VISITOR pattern [described in Gamma, E., et al., Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, Reading, Mass., 1995] is a well-known approach to implementing double dispatch in single-dispatch languages.
VISITOR encapsulates double-dispatch functionality in concrete Visitor subclasses of a Visitor class. Double dispatch occurs when an instance of an Element subclass (e.g., ConcreteElement) receives an Accept message with an object of type Visitor as a parameter. In response, Accept sends a message to the Visitor; exactly which message depends on the particular Element subclass. In effect, this message identifies the concrete Element to the concrete Visitor and invokes code that is specific to the ConcreteVisitor-ConcreteElement pairxe2x80x94thereby effecting double dispatch.
FIG. 1 shows a Unified Modeling Language (UML) diagram of a typical VISITOR implementation. This figure (and FIG. 2) may be seen in Gamma, E., et al., Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, Reading, Mass., 1995, p. 331-334, the disclosure of which is hereby incorporated by reference. FIG. 1 shows a Client object interacting with Visitor and Element (through ObjectStructure) classes. The Visitor class is a base class, and the ConcreteVisitor1 and ConcreteVisitor2 concrete classes are subclasses of Visitor. Similarly, Element is a base class, and ConcreteElementA and ConcreteElementB are concrete classes that are subclasses of Element. Visitor defines several methods (e.g., VisitConcreteElementA and VisitConcreteElementB) that the concrete classes inherit. Element also defines a method, Accept, that the subclasses of Element inherit. The subclasses of Element also define methods OperationA and OperationB.
FIG. 2 shows a sequence diagram that helps to explain how the class structure of FIG. 1 functions. The object, anObjectStructure, sends a message Accept(aVisitor) to the object aConcreteElementA. The object aConcreteElementA then can call VisitConcreteElementA, passing itself (i.e., aConcreteElementA) as a parameter. When the method VisitConcreteElementA runs, both the type of visitor (ConcreteVisitor1) and the type of element (ConcreteElementA) are known. Thus the operation that is performed, namely OperationA( ), is specific to these two objects. In the series of object interactions, anObjectStructure also sends a message Accept(aVisitor) to the object aConcreteElementB. The object aConcreteElementB then can call VisitConcreteElementB, passing itself as a parameter of type ConcreteElementB. When the method VisitConcreteElementB runs, both the type of visitor (ConcreteVisitor1) and the type of element (ConcreteElementB) are known. Thus the operation that is performed, namely OperationB( ), is specific to these two objects.
The VISITOR approach is statically type-safe, since the Visitor class declares Visit messages for each and every Element subclass. It works well under the assumption that the Element hierarchy is stable while the functionality that applies to it is not. New behavior can be added noninvasively by defining new concrete Visitor classes.
While VISITOR supports statically type-safe double dispatch in single-dispatch languages, it has at least two weaknesses. First, it produces a cyclic dependency between the Visitor and Element class hierarchies. Specifically, the Visitor base class refers to Element subclasses, and Element subclasses refer to the Visitor base class. As a result, changes to either hierarchy may require recompiling the other, the expense of which may be prohibitive in large software systems. Second, introducing a new Element subclass usually requires changing the Visitor base class. This aspect of VISITOR necessitates invasive change.
There are two workarounds to these problems in the prior art. ACYCLIC VISITOR [described in Martin, R. C., xe2x80x9cAcyclic Visitor,xe2x80x9d in Pattern Languages of Program Design 3, Martin, et al., eds., Addison-Wesley, Reading, Mass., 1998, the disclosure of which is incorporated herein by reference] removes method names from the Visitor class, declaring them solely in its subclasses. An Element subclass determines the message to send to a concrete Visitor using a run-time type test in its Accept method. While ACYCLIC VISITOR breaks the cyclic dependency, it does so at the expense of static type safety in all Visitor subclasses.
A catchall operation [described in Vlissides, J., Pattern Hatching: Design Patterns Applied, Addison-Wesley, Reading, Mass., 1998, the disclosure of which is incorporated herein by reference] primarily addresses the second weakness. It adds a method to the Visitor class that takes an Element as an argument. A new concrete Element subclass of Element will invoke this method in its Accept method, thereby avoiding the need to change the Visitor class. A concrete Visitor subclass that implements specialized code for this concrete Element must do so in the catchall operation, again using run-time type tests to differentiate each new Element subclass from every other. This too compromises static type safety, although only that of new Element subclasses, which are those Element subclasses added after defining the Visitor interface.
The catchall thus offers a greater degree of type safety than ACYCLIC VISITOR under the assumption that the Element hierarchy is relatively stable while the functionality that applies to it is not. The catchall requires a run-time type test for each new Element subclass, whereas ACYCLIC VISITOR requires a run-time type test for every Visitor subclass.
Both workarounds introduce an addition problem of cost. The overhead associated with the run-time type tests is proportional either to the total number of Visitor subclasses (in the case of ACYCLIC VISITOR) or to the number of new Element subclasses (in the catchall case). This cost is intolerable in some applications.
As a result of these problems, the discussed approaches are not effective for systems that require extensible, efficient, and statically type-safe double dispatch. A need exists for an extensible double-dispatch mechanism for single-dispatch languages that offers improved performance and static type safety.
In accordance with the aforementioned needs, the present invention is directed to an improved method and implementation of double dispatch for a program written in a single-dispatch object-oriented programming language.
In a first aspect of the invention, the present invention extends the VISITOR pattern to increase extensibility and efficiency. In particular, it applies the VISITOR pattern twice. The first application provides clients with the Visitor and Element interfaces devoid of references to subclasses or descendant classes: Visitor defines a single Visit operation taking a parameter of type Element, and Element defines a single Accept operation taking a parameter of type Visitor. The second application of VISITOR introduces the concrete descendant classes requiring double dispatch. These are added in pairs of hierarchies, each pair consisting of a hierarchy of classes rooted in an abstract subclass of Visitor, and a hierarchy of classes rooted in an abstract subclass of Element. The abstract subclass of Element introduces an Accept operation taking a parameter of type corresponding to the accompanying abstract subclass of Visitor. Akin to the VISITOR pattern, the abstract subclass of Visitor adds a Visit operation for each accompanying concrete descendant of the abstract Element subclass.
These two applications of VISITOR are connected through a run-time type test in the Visit operation of the Visitor class as implemented by the abstract Visitor subclass. This implementation selects among the pairs of hierarchies of classes requiring double dispatch. Apart from this run-time type test, static type safety is preserved within the two applications of VISITOR. Because the number of pairs is smaller than the total number of different double-dispatch operations required (and likely far smaller), the amount of run-time type testing is substantially less than that of the prior art.
In a second aspect of the present invention, a Visit operation is added that takes an instance of an abstract Element descendant as a parameter to avert an infinite recursion in the event that a new Element descendent is introduced after the Element and Visitor interfaces are defined.
In a third aspect of the present invention, one or more Visit operations in one or more abstract classes implement nontrivial default behavior.
A more complete understanding of the present invention, as well as further features and advantages of the present invention, will be obtained by reference to the following detailed description and drawings.